public class Solution68 {

    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> res = new ArrayList<>();
        int curWidth = 0; // 当前行的宽度
        int curWord = 0; // 当前单词
        int lastWord = 0;
        int wordNum = 0;
        boolean flag = false;
        while (curWord < words.length) {
            // 贪心获得一行没有空格情况下能够塞入的最大的单词数
            if ((curWidth + words[curWord].length()) <= maxWidth && !flag) {
                curWidth += words[curWord].length();
                wordNum++;
                curWord++;
                if (curWord == words.length) {
                    curWord--;
                    flag = true;
                }
            }
            // 每两个单词之间至少有一个空格
            else {
                if (!flag) curWord--;
                // 最后一行
                while ((curWidth + wordNum - 1) > maxWidth) {
                    curWidth -= words[curWord].length();
                    wordNum--;
                    curWord--;
                }
                // 每行的单词数确定之后。分配每行的空格
                if (curWord == words.length - 1) {
                    String t="";
                    for(int i=lastWord;i<curWord;i++){
                        t+=words[i];
                        t+=" ";
                    }
                    t+=words[curWord];
                    for(int i=t.length();i<maxWidth;i++){
                        t+=" ";
                    }
                    res.add(t);
                } else {
                    // 算上必须的一个空格，curWord+1个单词需要curWord个空格
                    curWidth += (wordNum - 1);
                    int leftWidth = maxWidth - curWidth;
                    int perWidth = 0;
                    if (wordNum != 1) {
                        // 四舍五入
                        if(leftWidth % ((wordNum - 1))==0)
                        perWidth= (int) Math.round((double) (leftWidth / (wordNum - 1)));
                        else{
                            perWidth= (int) Math.round((double) (leftWidth / (wordNum - 1)))+1;
                        }
                        String temp = "";
                        for (int i = lastWord; i < curWord - 1; i++) {
                            temp += words[i];
                            temp += " ";
                            for (int j = 0; j <perWidth; j++) {
                                temp += " ";
                            }
                            leftWidth-=perWidth;
                            if(leftWidth % ((wordNum - 1))==0)
                                perWidth= (int) Math.round((double) (leftWidth / (wordNum - 1)));
                            else{
                                perWidth= (int) Math.round((double) (leftWidth / (wordNum - 1)))+1;
                            }

                        }
                        temp += words[curWord - 1];
                        temp += " ";
                        for (int i = 0; i < leftWidth; i++) {
                            temp += " ";
                        }

                        temp += words[curWord];
                        res.add(temp);
                    } else {
                        String temp = "";
                        temp += words[curWord];
                        for (int i = temp.length(); i < maxWidth; i++) {
                            temp += " ";
                        }
                        res.add(temp);
                    }
                }
                curWidth = 0;
                curWord++;
                lastWord = curWord;
                wordNum = 0;
                flag = false;
            }
        }
        return res;
    }
}